/****************************************************************
 * 双链表
 * 
 ****************************************************************/
#include <cstdlib>
typedef int ElemType;                        //定义元素的类型

/**
 * 双链表中结点类型的描述
 * 
 * */
typedef struct DNode{                       //定义双链表结点类型
    ElemType data;                          //数据域
    struct DNode *prior, *next;             //前驱和后继的指针
}DNode, *DLinkList;

/**
 * 初始化双链表
 * 
 * */
bool InitDLinkList(DLinkList &L){
    L = (DNode *)malloc(sizeof(DNode));     //分配一个头结点
    if(L == NULL)                           //内存分配失败
        return false;
    L->prior = NULL;                        //头结点的prior永远指向NULL
    L->next = NULL;                         //头结点之后暂时还没有头结点

    return true;
}

/**
 * 判断双链表是否为空
 * */
bool Empty(DLinkList L){
    return (L->next == NULL);
}

/**
 * 双链表的插入操作
 * 
 * 将结点 *s 插入到结点 *p 之后
 * */
bool InsertNextDNode(DNode *p, DNode *s){
    if(p == NULL || s == NULL)                //非法参数
        return false;
    s->next = p->next;
    if(p->next != NULL)                     //当p结点的后继没有结点时，它没有前驱指针
        p->next->prior = s;
    s->prior = p;
    p->next = s;
    
    return true;
}

/**
 * 双链表的删除操作
 * 
 * 删除双链表中结点 *p 的后继结点 *q
 * 
 * */

bool ListDelete(DNode *p){
    if(p == NULL || p->next == NULL)          //非法参数
        return false;
    DNode *q = p->next;
    p->next = q->next;
    if(q->next != NULL)                 //当q结点的后继为NULL时，它没有前驱指针
        q->next->prior = p;
    free(q);                            //释放结点空间

    return true;
}

/**
 * 销毁一个单链表
 * */
void DestoryList(DLinkList &L){
    //循环释放各个数据结点
    while(L->next != NULL){
        ListDelete(L);
    }

    free(L);                            //释放头结点
    L = NULL;                           //头指针指向NULL
}